package solution;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * <a href="https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=188&&tqId=38609&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC37 合并区间</a>
 *
 * @author or2
 * @Description 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 * @create 2021年09月05日 时间: 18:41
 */
public class MergeNC37 {

    /**
     * Definition for an interval.
     */
    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//        根据 起始点 对区间排序
        intervals.sort(Comparator.comparingInt(o -> o.start));
//        判断当前区间是否可以和下一区间合并
        for (int i = 0; i < intervals.size() - 1; i++) {
            Interval cur = intervals.get(i);
            Interval curNext = intervals.get(i + 1);
//            可以合并 (>= 相等也要合并)
            if (cur.end >= curNext.start) {
                Interval newInter = new Interval(Math.min(cur.start, curNext.start), Math.max(cur.end, curNext.end));
                intervals.set(i + 1, newInter);
//                循环自动 +1, 会跳过元素
                intervals.remove(i--);
            }
        }

        return intervals;
    }
}


